/**
 * @file     majorityElement.ts
 * @brief    [169. 多数元素](https://leetcode.cn/problems/majority-element/)
 * @author   Zhu
 * @date     2022-10-30 20:18
 */

// 投票法
function majorityElement(nums: number[]): number {
    let winner;
    let count = 0;
    for (const num of nums) {
        if (num === winner || winner == undefined) {
            winner = num;
            count++;
        } else if (count > 0) {
            count--;
        } else {
            winner = num;
            count++;
        }
    }

    return winner;
}

// 分治
function majorityElement(nums: number[]): number {
    function count(val: number, start: number, end: number) {
        let amount = 0;
        for (let i = start; i <= end; i++) {
            if (nums[i] === val) amount++;
        }
        return amount;
    }
    function findMajority(start: number, end: number): number {
        if (start === end) return nums[start];

        let mid = Math.floor((start + end) / 2);
        let leftMajority = findMajority(start, mid);
        let rightMajority = findMajority(mid + 1, end);
        if (leftMajority === rightMajority) return leftMajority;

        let leftMajorityAmount = count(leftMajority, start, mid);
        let rightMajorityAmount = count(rightMajority, mid + 1, end);
        return leftMajorityAmount > rightMajorityAmount
            ? leftMajority
            : rightMajority;
    }

    return findMajority(0, nums.length - 1);
}
